21. Merge Two Sorted Lists

Question

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

- The number of nodes in both lists is in the range [0, 50].
- -100 <= Node.val <= 100
- Both list1 and list2 are sorted in non-decreasing order.

---

Approach

1. If both Lists are empty, return empty. If any of them are empty, return the non empty one.
2. Create a new List node head (to return later) and a copy curr.
3. Traverse the linked list until the end of either list, compare the value of list1 and list2, then link the smaller node to curr.
4. Move to the next node if the element from that list is used.
5. We might still have some leftovers nodes since we exited step 3 when either one of it runs out.
6. It is not necessary to traverse anymore, simply link the whole remaining list behind curr.

Solution

//Definition for singly-linked list.
type ListNode struct {
    Val int
    Next *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    if list1 == nil && list2 == nil{
        return nil;
    } else if list1 == nil{
        return list2
    }else if list2 == nil{
        return list1;
    }
    
    head := &ListNode{0,nil}
    curr := head
    
    for {
        if (list1 == nil || list2 == nil){
            break
        }
        
        if list1.Val < list2.Val{
            curr.Next = list1
            list1 = list1.Next
        }else{
            curr.Next = list2
            list2 = list2.Next
        }
        curr = curr.Next
    }
    
    if(list1 != nil){
        curr.Next = list1
    }else{
        curr.Next = list2
    }
    return head.Next;
}